#define _CRT_SECURE_NO_WARNINGS 1	
#include"SeqList.h"

void SeqListInit(SL* ps)	//顺序表初始化
{
	assert(ps);
	ps->data = NULL;	//指针置空
	ps->size = ps->capacity = 0;	//数据、容量归零
}

void SeqListDestroy(SL* ps)	//销毁顺序表
{
	assert(ps);
	free(ps->data);	//直接释放顺序表数据域
	SeqListInit(ps);	//代码复用
}

void SeqListPrint(SL* ps)	//打印顺序表
{
	assert(ps);
	size_t i = 0;	//定义一个同样类型的变量i
	//配合size进行打印
	for (i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);	//ps->data[i]相当于我们熟悉的arr[i]
	printf("\n");	//全部输出结束后，可以换行
}

void decideCapacity(SL* ps)	//判断容量
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//两倍扩容
		SLDatatype* tmp = (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) * newcapacity);
		assert(tmp);	//断言，可能存在扩容失败的情况
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
}
void SeqListPushBack(SL* ps, SLDatatype x)		//尾插
{
	assert(ps);
	decideCapacity(ps);	//判断是否需要扩容

	ps->data[ps->size++] = x;	//尾插成功
	//SeqListInsert(ps, ps->size, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopBack(SL* ps)	//尾删
{
	assert(ps);
	assert(ps->size > 0);	//需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的
	ps->size--;	//有效数据-1，就是尾删
	//SeqListErase(ps, ps->size - 1);	//可以使用任意位置删除，替代删除
}

void SeqListPushFront(SL* ps, SLDatatype x)		//头插
{
	assert(ps);	//断言，防止空指针
	decideCapacity(ps);	//判断扩容

	//先把数据整体往后挪动，再头插
	size_t end = ps->size;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}
	ps->data[end] = x;
	ps->size++;
	//SeqListInsert(ps, 0, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopFront(SL* ps)	//头删
{
	assert(ps);
	assert(ps->size > 0);

	//同头插原理一样，需要把数据整体往前挪动
	size_t begin = 0;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;	//有效元素-1，就可以实现头删
	//SeqListErase(ps, 0);	//可以使用任意位置删除，替代删除
}

void SeqListInsert(SL* ps, int pos, SLDatatype x)	//任意插
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos <= ps->size);
	decideCapacity(ps);	//判断容量

	//原理有点类似头插，不过终止条件依赖于pos
	size_t end = ps->size;
	while (end > (size_t)pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)	//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos < ps->size);

	//类似于头删
	size_t begin = (size_t)pos;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;
}

int SeqListFind(SL* ps, SLDatatype x)	//查找元素
{
	assert(ps);
	size_t i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
			return i;
	}

	return -1;	//没有找到目标元素
}
